package com.datastructure.test.tr;

import java.util.*;

public class Main {
    /**
     * 统计字符串中的回文字符子串个数
     * @param
     * @return int整型
     */
    public static void main(String[] args) {
        Main solution = new Main();
        String s= "abc";
        solution.cntPalindromicSubstrings(s);
    }
    ArrayList<ArrayList<Byte>> res = new ArrayList<>();
    public int cntPalindromicSubstrings (String s) {
        // write code here
        int result=0;
        boolean tag=true;
        byte[] bytes = s.getBytes();
        byte[] bytes1=new byte[bytes.length];
        for (int i = bytes.length; i >0; i--) {
            bytes1[bytes.length-i]=bytes[i-1];
        }
        ArrayList<ArrayList<Byte>> data;
        ArrayList<ArrayList<Byte>> data1;
        data=subsets(bytes);
        data1=subsets(bytes1);
        for (List<Byte> datum : data) {
            for (List<Byte> byteArrayList : data1) {
                if(datum.size()==byteArrayList.size()){
                    for (int i = 0; i < datum.size(); i++) {
                        if(!datum.get(i).equals(byteArrayList.get(i))){
                            tag=false;
                            break;
                        }else {
                            tag=true;
                        }
                    }
                }
                if(tag){
                    result++;
                }
            }
        }
        result=result/36;
        return result;
    }
    public ArrayList<ArrayList<Byte>> subsets(byte[] S) {
        LinkedList<Byte> track = new LinkedList<>();
        back(S, 0, track);
        res.remove(0);
        return res;
    }
    public void back(byte[] S, int start, LinkedList<Byte> track){
        res.add(new ArrayList<>(track));
        for(int i = start; i < S.length; i++){
            track.add(S[i]);
            back(S, i+1, track);
            //撤销 回溯
            track.removeLast();
        }
    }
}
